public class LeetCode377 {
    /**
     * 更 518 很像
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        //数组长度为0直接返回
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //初始化动态数组
        int[] dp = new int[target + 1];
        dp[0] = 1;

        // 遍历从1到target的每一个值
        for (int i = 1; i <= target; i++) {
            // 对于每个值i，遍历nums数组中的每个数num
            for (int num : nums) {
                if (i >= num) {
                    // 更新dp[i]，增加dp[i - num]的值
                    dp[i] += dp[i - num];
                }
            }
        }
        //// 返回dp[target]，即达到target的不同组合的数量
        return dp[target];
    }
}
